//
//  Problem983.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 983. 最低票价
 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

 火车票有三种不同的销售方式：

 一张为期一天的通行证售价为 costs[0] 美元；
 一张为期七天的通行证售价为 costs[1] 美元；
 一张为期三十天的通行证售价为 costs[2] 美元。
 通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

 返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

 示例 1：
     输入：days = [1,4,6,7,8,20], costs = [2,7,15]
     输出：11
     解释：
     例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
     在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
     在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
     你总共花了 $11，并完成了你计划的每一天旅行。
 示例 2：
     输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
     输出：17
     解释：
     例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
     在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
     你总共花了 $17，并完成了你计划的每一天旅行。

 提示：
     1 <= days.length <= 365
     1 <= days[i] <= 365
     days 按顺序严格递增
     costs.length == 3
     1 <= costs[i] <= 1000
 */
@objcMembers class Problem983: NSObject {
    func solution() {
        print(mincostTickets([1,4,6,7,8,20], [2,7,15]))
        
        print(mincostTickets([1,2,3,4,5,6,7,8,9,10,30,31], [2,7,15]))
    }
    
    /*
     动态规划
     1: 创建一个二维数组dp[m], m = days.count
     2: dp[i] 第i天花费了话费的最少值
     3: dp[i] = min(1天 7天 30天)
        3.1 1天 = costs[0] + dp[next(i+1)]
        3.2 7天 = costs[1] + dp[next(i+7)]
        3.3 30天 = costs[2] + dp[next(i+30)]
     */
    func mincostTickets(_ days: [Int], _ costs: [Int]) -> Int {
        if days.count == 1 {
            return costs[0]
        }
        
        var dp = Array(repeating: -1, count: days.count)
        return mincostTicketsDP(days, costs, &dp, 0)
    }
    
    func mincostTicketsDP(_ days: [Int], _ costs:[Int], _ dp: inout [Int], _ i: Int) -> Int {
        if i >= days.count {
            return 0
        }
        
        if dp[i] != -1 {
            return dp[i]
        }
        
        var value = Int.max
        // 1天
        value = min(value, costs[0] + mincostTicketsDP(days, costs, &dp, getNextPostion(days, i, 1)))
        // 7天
        value = min(value, costs[1] + mincostTicketsDP(days, costs, &dp, getNextPostion(days, i, 7)))
        // 30天
        value = min(value, costs[2] + mincostTicketsDP(days, costs, &dp, getNextPostion(days, i, 30)))
        
        dp[i] = value
        return value
    }
    
    func getNextPostion(_ days: [Int],  _ start: Int, _ day: Int) -> Int {
        if start >= days.count {
            return days.count
        }
        
        let nextDay = days[start] + day
        for i in start+1..<days.count {
            if days[i] >= nextDay {
                return i
            }
        }
        
        return days.count
    }
}
